package leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;

public class CombinationSum {

	public int count = 0;
	
	public static void main(String[] args) {
		CombinationSum sum = new CombinationSum();
//		int[] nums = {1, 2, 3, 4};
//		int target = 32;
//		System.out.println(sum.combinationSum4_2(nums, target));
		System.out.println(sum.combinationSum3(3, 9));
	}
	
	// TLE, 当target很大的时候会运行很长的时间
	public int combinationSum4(int[] nums, int target) {
		count = 0;
		if(nums == null || nums.length <= 0 || target < 0){
			return 0;
		}
		ArrayList<Integer> list = new ArrayList<Integer>();
		backtract(nums, target, list);
		return count;
	}
	
	public void backtract(int[] nums, int remain, ArrayList<Integer> list){
		if(remain < 0){
			return;
		}
		if(remain == 0){
			count++;
			System.out.println(list);
			return;
		}
		for (int i = 0; i < nums.length; i++) {
			list.add(nums[i]);
			backtract(nums, remain - nums[i], list);
			list.remove(list.size() - 1);
		}
	}
	
	int[] dp;
	//我们知道dp[target] = dp[target - nums[0]] + dp[target - nums[1]] + ...
	//相当于是一个累加的过程，比如[1 2 3] target = 4
	//dp[4] = dp[4 - 1] + dp[4 - 2] + dp[4 - 3]
	public int combinationSum4_2(int[] nums, int target) {
		if(nums == null || nums.length <= 0 || target < 0){
			return 0;
		}
		dp = new int[target + 1];
		Arrays.fill(dp, -1);
		dp[0] = 1;  //initial condition
		helper(nums, target);
		return dp[target];
	}
	private int helper(int[] nums, int target) {
	    if (dp[target] != -1) {
	        return dp[target];
	    }
	    int res = 0;
	    for (int i = 0; i < nums.length; i++) {
	        if (target >= nums[i]) {
	            res += helper(nums, target - nums[i]);
	        }
	    }
	    dp[target] = res;
	    return res;
	}
	
	//Find all possible combinations of k numbers that add up to a number n, 
	//given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers.
	//Input: k = 3, n = 7
	//Output:
	//[[1,2,4]]
	
	List<List<Integer>> res = new ArrayList<>();
	List<Integer> list = new ArrayList<>();
	int[] nums = {1, 2, 3, 4, 5, 6, 7, 8, 9};
	public List<List<Integer>> combinationSum3(int k, int n) {
        backtrack(nums, n, 0, 0, k, n);
        System.out.println(res);
        return res;
    }
	
	public void backtrack(int[] nums, int remain, int start, int numberCount, int k, int n){
		if(remain < 0){
			return;
		}
		if(remain == 0 && numberCount == k){
			res.add(new ArrayList<>(list));
		}else if(remain == 0 || numberCount == k){
			return;
		}
		for (int i = start; i < nums.length; i++) {
			list.add(nums[i]);
			backtrack(nums, remain - nums[i], i + 1, numberCount + 1, k, n);
			list.remove(list.size() - 1);
		}
	}
}
